package lc.q1_50;

/**
 * 乘法运算
 */
public class Q43 {


    public String multiply2(String num1, String num2) {
        // 最大位数len(num1） + len(num2) 原因事可以取比num1位数更大的最小值和num2位数更大的最小值，他们的乘积nu刚好事len(num1)+len(num2)+1位
        int[] results = new int[num1.length() + num2.length()];
        // 对于i*j的所在位置可以知道
        // 先不考虑进位，直到最后算完再考虑
        for (int i = 0; i < num1.length(); i++) {
            final int v1 = Character.getNumericValue(num1.charAt(num1.length() - i -1));
            for (int j = 0; j < num2.length(); j++) {
                final int v2 = Character.getNumericValue(num2.charAt(num2.length() - j - 1));
                int result = v1 * v2 + results[i+j];
                results[i+j] = result;
            }
        }
        // 进位
        final StringBuilder sb = new StringBuilder();
        for (int i = 0; i < results.length - 1; i++) {
            // 考虑进位
            final int result = results[i];
            sb.append(result % 10);
            results[i+1] += result / 10;
        }
        sb.append(results[results.length -1]);
        final StringBuilder reverse = sb.reverse();
        while (reverse.charAt(0) == '0' && reverse.length() != 0) {
            reverse.deleteCharAt(0);
        }
        return reverse.toString();
    }


    public String multiply(String num1, String num2) {
        // 思路1，分治法
        // 思路2，考虑每一位数的来源，个人数来源于个人相乘，十位数来源于个人十位相册和个人相册进1，显然
        final int len1 = num1.length();
        final int len2 = num2.length();
        if (len1 < len2) {
            return multiply(num2, num1);
        }
        if (len2 == 0) {
            return "0";
        }
        if (len1 == 1) {
            final int c1 = num1.charAt(0) - '0';
            final int c2 = num2.charAt(0) - '0';
            return String.valueOf(c1 * c2);
        }
        // 分治法
        final String A = num1.substring(0, len1 / 2);
        final String B = num2.substring(0, len2 / 2);
        final String C = num1.substring(len1 / 2, len1);
        final String D = num2.substring(len2 / 2, len2);
        String left = completeZero(multiply(A, B), C.length() + D.length());
        String right = completeZero(multiply(C, D), 0);
        String leftRight = completeZero(multiply(A, D), C.length());
        String rightLeft = completeZero(multiply(C, B), D.length());
        // 对这四个数进行处理
        return plus(plus(left, right), plus(leftRight, rightLeft));
    }

    private String completeZero(String num, int zeroSize) {
        if ("0".equals(num)) {
            return num;
        }
        final StringBuilder sb = new StringBuilder(num);
        for (int i = 0; i < zeroSize; i++) {
            sb.append('0');
        }
        return sb.toString();
    }

    private String plus(String num1, String num2) {
        int i = num1.length();
        int j = num2.length();
        int jw = 0;
        StringBuilder sb = new StringBuilder();
        while (i > 0 && j > 0) {
            final int iNum = Character.getNumericValue(num1.charAt(i -1));
            final int jNum = Character.getNumericValue(num2.charAt(j - 1));
            int sum = iNum+jNum+jw;
            sb.append(sum % 10);
            jw = sum / 10;
            i --;
            j --;
        }
        if (i > 0) {
            // completeRemain
            completeRemain(sb, num1,jw, i);
        } else if (j > 0) {
            // completeRemain
            completeRemain(sb, num2, jw,j);
        } else {
            if (jw != 0) {
                sb.append(jw);
            }
        }

        return sb.reverse().toString();
    }

    private void completeRemain(StringBuilder sb, String nums,int jw, int remain) {
        for (int i = remain-1; i >= 0; i--) {
            final int value = Character.getNumericValue(nums.charAt(i)) + jw;
            sb.append(value % 10);
            jw = value / 10;
        }
        if (jw != 0) {
            sb.append(jw);
        }
    }

    public static void main(String[] args) {
        final Q43 q43 = new Q43();


        final String multiply = q43.multiply2("10", "99");
        System.out.println(multiply);
        System.out.println(q43.multiply2("123456789", "987654321"));
        System.out.println(q43.multiply("123456789", "987654321"));

    }

}
